package com.future.offer;

/**
 * Description: 剑指 Offer II 004. 只出现一次的数字
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
 * <p>
 * 你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/single-number-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2023/2/1 09:25
 */
public class Solution_004 {

    public static void main(String[] args) {
        int[] nums = new int[]{0, 1, 0, 1, 0, 1, 100};
        // nums = new int[]{2, 2, 2, 3};
        nums = new int[]{30000, 500, 100, 30000, 100, 30000, 100};
        nums = new int[]{-2, -2, 1, 1, 4, 1, 4, 4, -4, -2};
        System.out.println(singleNumber(nums));
        System.out.println("=======");
        test();
    }

    private static void test() {
        int n = -11110;
        System.out.println(n + "==>" + Integer.toBinaryString(n));
        System.out.println(-n + "==>" + Integer.toBinaryString(-n));
        int i = 2;
        System.out.println((n >> i) & 1);
        System.out.println(n & (1 << i));

    }

    public static int singleNumber(int[] nums) {
        int N = nums.length;
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int countOne = 0;
            for (int j = 0; j < N; j++) {
                /**
                 * countOne += (nums[j] & (1 << i));
                 * 不通过用例 [-2,-2,1,1,4,1,4,4,-4,-2]
                 * 解释：假设有个数的二进制是01011111
                 * 当访问到第4为(从右往左0,1,..数)
                 * 我们要做的是提取对应数位上的数是否是1，而不是对应的值(0位置数是1，值为1；1位置数是1，值为2。我们要做的实际就是提取数1)
                 * 而(nums[j] & (1 << i))实际上提取的是对应位置转成十进制后的值了，所以是错的
                 * 比如 01011111 & (1<<2)=7，我们要的实际就是1
                 */
                // countOne += (nums[j] & (1 << i));
                countOne += ((nums[j] >> i) & 1);
            }
            if (countOne % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }


}
